/**
 * @link https://leetcode.cn/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150
 */
function canConstruct(ransomNote: string, magazine: string): boolean {
  let dict: { [key in string]: number } = {};
  for (let i = 0; i < magazine.length; i++) {
    if (dict.hasOwnProperty(magazine[i])) {
      dict[magazine[i]] += 1;
    } else {
      dict[magazine[i]] = 1;
    }
  }
  for (let i = 0; i < ransomNote.length; i++) {
    if (dict.hasOwnProperty(ransomNote[i])) {
      dict[ransomNote[i]] -= 1;
      if (dict[ransomNote[i]] < 0) {
        return false;
      }
    } else {
      return false;
    }
  }
  return true;
}

/**
 * @link https://leetcode.cn/problems/isomorphic-strings/?envType=study-plan-v2&envId=top-interview-150
 */
function isIsomorphic(s: string, t: string): boolean {
  let dict: { [key: string]: string } = {};
  let p = 0;
  while (p < s.length) {
    if (dict.hasOwnProperty(s[p])) {
      if (dict[s[p]] !== t[p]) return false;
    } else {
      if (Object.keys(dict).some((k) => dict[k] === t[p])) return false;
      dict[s[p]] = t[p];
    }
    p += 1;
  }
  return true;
}

/**
 * @link https://leetcode.cn/problems/word-pattern/?envType=study-plan-v2&envId=top-interview-150
 */
function wordPattern(pattern: string, s: string): boolean {
  let sList = s.trim().split(" ");
  let dict: {
    [key: string]: string;
  } = {};
  if (pattern.length !== sList.length) return false;
  console.log(sList);
  let p = 0;
  while (p < pattern.length) {
    if (dict.hasOwnProperty(pattern[p])) {
      if (dict[pattern[p]] !== sList[p]) return false;
    } else {
      if (Object.keys(dict).some((k) => dict[k] === sList[p])) return false;
      dict[pattern[p]] = sList[p];
    }
    p += 1;
  }

  return true;
}

/**
 * @link https://leetcode.cn/problems/valid-anagram/?envType=study-plan-v2&envId=top-interview-150
 */
function isAnagram(s: string, t: string): boolean {
  let dicts: {
    [key: string]: number;
  } = {};
  if (s.length !== t.length) return false;
  // hash table
  // for (let i = 0; i < s.length; i++) {
  //   if (dicts.hasOwnProperty(s[i])) {
  //     dicts[s[i]] += 1;
  //   } else {
  //     dicts[s[i]] = 1;
  //   }
  // }
  // for (let i = 0; i < t.length; i++) {
  //   if (dicts.hasOwnProperty(t[i])) {
  //     dicts[t[i]] -= 1;
  //     if (dicts[t[i]] < 0) return false;
  //   } else {
  //     return false;
  //   }
  // }

  // sort
  s = s
    .split("")
    .sort((a: any, b: any) => a.charCodeAt(0) - b.charCodeAt(0))
    .join("");
  t = t
    .split("")
    .sort((a: any, b: any) => a.charCodeAt(0) - b.charCodeAt(0))
    .join("");
  if (s !== t) return false;
  return true;
}

/**
 * @link https://leetcode.cn/problems/group-anagrams/?envType=study-plan-v2&envId=top-interview-150
 */
function groupAnagrams(strs: string[]): string[][] {
  const sortedWord = (s: string) => {
    return s
      .split("")
      .sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0))
      .join("");
  };
  let dic: {
    [key: string]: string[];
  } = {};
  let res: string[][] = [];
  for (const word of strs) {
    if (dic.hasOwnProperty(sortedWord(word))) {
      dic[sortedWord(word)].push(word);
    } else {
      dic[sortedWord(word)] = [word];
    }
  }

  Object.keys(dic).map((k) => res.push(dic[k]));
  return res;
}

/**
 * @link https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150
 */
function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    let other = nums.indexOf(target - nums[i]);
    console.log(other);
    if (other !== i && other > -1) {
      return [i, other];
    }
  }
  return [];
}

/**
 * @link https://leetcode.cn/problems/happy-number/?envType=study-plan-v2&envId=top-interview-150
 */
function isHappy(n: number): boolean {
  let dict: { [key: number]: number } = {};
  let dict_existed: { [key: number]: number } = {};
  for (let i = 0; i < 10; i++) {
    dict[i] = i * i;
  }
  // console.log(dict);
  let tmp = n;
  const nextNum = (num: number) => {
    let ans = 0;
    while (num > 0) {
      ans += dict[num % 10];
      num = Math.floor(num / 10);
    }
    return ans;
  };
  while (tmp !== 1) {
    console.log(nextNum(tmp));
    let t = nextNum(tmp);
    if (dict_existed.hasOwnProperty(t) && dict_existed[t] === tmp) return false;
    dict_existed[t] = tmp;
    tmp = t;
  }

  return true;
}

/**
 * @link https://leetcode.cn/problems/contains-duplicate-ii/?envType=study-plan-v2&envId=top-interview-150
 */
function containsNearbyDuplicate(nums: number[], k: number): boolean {
  if (nums.length < 2) return false;
  let s = 0;
  let e = 1;
  while (s < nums.length - 1) {
    while (e < nums.length && nums[s] !== nums[e]) {
      e += 1;
    }
    if (e < nums.length && e - s <= k) {
      return true;
    }
    s += 1;
    e = s + 1;
  }

  return false;
}

/**
 * @link https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-interview-150
 */
function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;
  nums.sort((a, b) => a - b);

  nums = Array.from(new Set(nums));
  console.log(nums);
  let s = 1;
  let tmp = 1;
  let ans = 1;
  while (s < nums.length) {
    if (nums[s] - 1 === nums[s - 1]) {
      tmp += 1;
    } else {
      ans = Math.max(tmp, ans);
      tmp = 1;
    }
    s += 1;
  }

  return Math.max(tmp, ans);
}

export default {
  canConstruct,
  isIsomorphic,
  wordPattern,
  isAnagram,
  groupAnagrams,
  twoSum,
  isHappy,
  containsNearbyDuplicate,
  longestConsecutive,
};
